package goleetcode

func maximumPrimeDifference(nums []int) int {
	arr := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		if isPrime(nums[i]) {
			arr[i] = 1
		} else {
			arr[i] = 0
		}
	}
	i, j := 0, len(nums) - 1
	for i < len(nums) {
		if arr[i] == 1 {
			break
		}
		i++
	}
	for j > 0 {
		if arr[j] == 1 {
			break
		}
		j--
	}
	return j - i
}

func isPrime(n int) bool {
	if n <= 1 {
		return false
	}
	if n <= 3 {
		return true
	}
	if n % 2 == 0 || n % 3 == 0 {
		return false
	}
	for i := 5; i * i <= n; i += 6 {
		if n % i == 0 || n % (i + 2) == 0 {
			return false
		}
	}
	return true
}


func maximumPrimeDifference2(nums []int) int {
	primes := map[int]bool{
		2: true,
		3: true,
		5: true,
		7: true,
		11: true, 13:true, 17: true, 19: true, 23: true, 29: true, 31: true,
		37: true, 41: true, 43: true, 47: true, 53: true, 59: true, 61: true,
		67: true, 71: true, 73: true, 79: true, 83: true, 89: true, 97: true,
	}
	first := -1
	ans := 0
	for i := 0; i < len(nums); i++ {
		if primes[nums[i]] {
			if first != -1 {
				ans = max(ans, i - first)
			} else {
				first = i
			}
		}
	}
	return ans
}